package leetcode.p331;

/**
 * @author: trtan
 * @create: 2021-04-08 19:09
 * @description:
 **/
public class VerifyBinaryTree {
    public static void main(String[] args) {
        String s =  "#";
        boolean validSerialization = new VerifyBinaryTree().isValidSerialization(s);
        System.out.println(validSerialization);
    }

    public boolean isValidSerialization(String preorder) {
        if ("#".equals(preorder)) {
            return true;
        }
        String[] nodes = preorder.split(",");
        int n = nodes.length;
        int total = 0;
        for (int i = 0; i < n; i++) {
            if ("#".equals(nodes[i])) {
                /** 如果第一个就是#号，直接结束 */
                if (i == 0) {
                    return false;
                } else {
                    // 可以填充的#号数量减1
                    total--;
                    //假设在没有遍历完成前total为0，即剩下的节点没有地方再放了
                    if (total == 0) {
                        if (i == n - 1) {
                            return true;
                        } else {
                            return false;
                        }
                    }
                }
            } else {
                // 第一个节点直接拥有两个空结点
                if (i == 0) {
                    total += 2;
                } else {
                    //后面的结点，每新增一个占用一个结点，新增两个结点，故新增一个结点
                    total++;
                }
            }
        }
        return false;
    }
}
